/**
 * 
 * 链表相加(二)
 * 描述

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
数据范围：
0
≤
n
,
m
≤
1000000
0≤n,m≤1000000，链表任意值 
0
≤
v
a
l
≤
9
0≤val≤9
要求：空间复杂度 
O
(
n
)
O(n)，时间复杂度 
O
(
n
)
O(n)

例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
 */
public class 链表相加2 {
    
    public static void main(String[] args) {
        
        // 链表 1：7->2->4->3
        ListNode l1 = new ListNode(9);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(7);

        // 链表 2：5->6->4
        ListNode l2 = new ListNode(6);
        l2.next = new ListNode(3);

        ListNode node = addInList(l1, l2);

        ListNode resultNode = reverseList(node);

        System.err.println(resultNode.toString());

    }

    private static ListNode addIntSubList(ListNode reverHead1, ListNode reverHead2, boolean moreTen, ListNode curr, ListNode root){

        if(null!=reverHead1 && null!=reverHead2){
            int sum = reverHead1.val + reverHead2.val + (moreTen ? 1 : 0);
            if(sum >= 10){
                sum -= 10;
                moreTen = true;
            } else {
                moreTen = false;
            }
            curr.next = new ListNode(sum);
            curr = curr.next;
            reverHead1 = reverHead1.next;
            reverHead2 = reverHead2.next;

            return addIntSubList(reverHead1, reverHead2, moreTen, curr, root);
        } else if(null==reverHead1 && null!=reverHead2){

            int sum = reverHead2.val + (moreTen ? 1 : 0);
            if(sum >= 10){
                sum -= 10;
                moreTen = true;
            } else {
                moreTen = false;
            }
            curr.next = new ListNode(sum);
            curr = curr.next;
            reverHead1 = null;
            reverHead2 = reverHead2.next;

            return addIntSubList(null, reverHead2, moreTen, curr, root);

        } else if(null!=reverHead1 && null==reverHead2){

            int sum = reverHead1.val + (moreTen ? 1 : 0);
            if(sum >= 10){
                sum -= 10;
                moreTen = true;
            } else {
                moreTen = false;
            }
            curr.next = new ListNode(sum);
            curr = curr.next;
            reverHead1 = reverHead1.next;
            reverHead2 = null;

            return addIntSubList(reverHead1, null, moreTen, curr, root);

        } 

        if(moreTen){

            curr.next = new ListNode(1);
            curr = curr.next;
            moreTen = false; 
        }

        return root.next;



    }

    private static ListNode addInList (ListNode head1, ListNode head2) {
        // write code here

        ListNode reverHead1 = reverseList(head1);
        ListNode reverHead2 = reverseList(head2);

        boolean moreTen = false;

        ListNode root = new ListNode(0);
        ListNode curr = root;
        
        ListNode result = addIntSubList(reverHead1, reverHead2, moreTen, curr, root);

        return result;
    }

    private static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr!= null) {
            ListNode nextNode = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextNode;
        }
        return prev;
    }
}
